package test;

public class PriorityQueueDemo {

    private int[] array = new int[100];
    private int size = 0;

    public void shiftDown(int[] array, int parent) {
        int child = 2 * parent + 1;
        while (child < size) {
            // 如果右孩子存在，找到左右孩子中较小的孩子，用child进行标记
            if (child + 1 < size && array[child + 1] < array[child]) {
                child++;
            }
            // 如果双亲比其最小的孩子还小，说明该结构已经满足堆的特性了
            if (array[parent] <= array[child]) {
                break;
            } else {
                // 将双亲与较小的孩子交换
                int t = array[parent];
                array[parent] = array[child];
                array[child] = t;
                // parent中大的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
                parent = child;
                child = parent * 2 + 1;
            }
        }
    }

    public void shiftUp(int[] array, int child) {
        // 找到child的双亲
        int parent = (child - 1) / 2;
        while (child > 0) {
            // 如果双亲比孩子大，parent满足堆的性质，调整结束
            if (array[parent] <= array[child]) {
                break;
            } else {
                // 将双亲与孩子节点进行交换
                int t = array[parent];
                array[parent] = array[child];
                array[child] = t;
                // 小的元素向上移动，成为parent之后可能它的父节点仍然不满足要求，因此需要继续向上调整
                child = parent;
                parent = (child - 1) / 2;
            }
        }
    }

    public void offer(int e) {
        array[size++] = e;
        shiftUp(array, size - 1);
    }

    public int poll() {
        int oldValue = array[0];
        array[0] = array[--size];
        shiftDown(array, 0);
        return oldValue;
    }

    public int peek() {
        return array[0];
    }

    public static void main(String[] args) {
        PriorityQueueDemo pq = new PriorityQueueDemo();

        // 插入测试
        pq.offer(5);
        pq.offer(3);
        pq.offer(17);
        pq.offer(10);
        pq.offer(84);
        pq.offer(19);
        pq.offer(6);
        pq.offer(22);
        pq.offer(9);

        System.out.println("插入元素后，最小元素是: " + pq.peek());

        // 提取测试
        System.out.println("提取最小元素: " + pq.poll());
        System.out.println("提取最小元素: " + pq.poll());
        System.out.println("提取最小元素: " + pq.poll());

        // 再次插入测试
        pq.offer(2);
        pq.offer(15);

        System.out.println("再次插入元素后，最小元素是: " + pq.peek());

        // 再次提取测试
        System.out.println("提取最小元素: " + pq.poll());
        System.out.println("提取最小元素: " + pq.poll());

        // 打印剩余元素
        System.out.print("优先级队列中剩余的元素: ");
        while (pq.size > 0) {
            System.out.print(pq.poll() + " ");
        }
    }
}
